package cn.xaut.剑指offer.m01;

import java.util.HashSet;
import java.util.Set;

public class demo01 {

    // 160. 相交链表 1 双指针法
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode l1 = headA, l2 = headB;

        while (l1 != l2) {

            if (l1 == null)
                l1 = headB;
            else
                l1 = l1.next;

            if (l2 == null)
                l2 = headA;
            else
                l2 = l2.next;

        }
        return l1;
    }
    
    /*
        上述 while 循环内还可以这样写：
            l1 = (l1 == null) ? headB : l1.next;
            l2 = (l2 == null) ? headA : l2.next;
     */


    // 160. 相交链表 2  暴力解法
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {

        if (headA == null || headB == null)
            return null;

        ListNode l1 = headA, l2;
        while (l1 != null) {

            l2 = headB;
            while (l2 != null) {
                if (l1 == l2)
                    return l1;
                l2 = l2.next;
            }
            l1 = l1.next;
        }
        return null;
    }


    // 160. 相交链表 3  哈希表法
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {

        ListNode l1 = headA, l2 = headB;
        Set<ListNode> set = new HashSet<>();
        while (l1 != null) {
            set.add(l1);
            l1 = l1.next;
        }
        while (l2 != null) {
            if (set.contains(l2))
                return l2;
            l2 = l2.next;
        }
        
        return null;
    }
}
